// exercise-equivalent-binary-trees.go
package main

import "fmt"
import "golang.org/x/tour/tree"

// type Tree struct {
// 	Left  *Tree
// 	Value int
// 	Right *Tree
// }

// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。
func Walk(t *tree.Tree, ch chan int) {
	// 将所有的值从 tree 发送到 channel ch。
	walkImpl(t, ch)

	// 关闭channel
	close(ch)
}

// 递归取值
func walkImpl(t *tree.Tree, ch chan int) {
	if t == nil {
		return
	}

	walkImpl(t.Left, ch)
	ch <- t.Value
	walkImpl(t.Right, ch)
}

// Same 检测树 t1 和 t2 是否含有相同的值。
func Same(t1, t2 *tree.Tree) bool {
	w1, w2 := make(chan int), make(chan int)

	go Walk(t1, w1)
	go Walk(t2, w2)

	// 循环取出 channel 中存储的数据对比
	for {
		// channel 关闭后 ok1, ok2 会 变成 false
		v1, ok1 := <-w1
		v2, ok2 := <-w2

		// 检查是否是同时关闭的 channel
		if !ok1 || !ok2 {
			return ok1 == ok2
		}

		// 有一个值出现不同,即返回false
		if v1 != v2 {
			return false
		}
	}
}

func main() {
	fmt.Print("tree.New(1) == tree.New(1): ")
	if Same(tree.New(1), tree.New(1)) {
		fmt.Println("PASSED")
	} else {
		fmt.Println("FAILED")
	}

	fmt.Print("tree.New(1) != tree.New(2): ")
	if !Same(tree.New(1), tree.New(2)) {
		fmt.Println("PASSED")
	} else {
		fmt.Println("FAILED")
	}
}

/*
练习：等价二叉树
1. 实现 Walk 函数。

2. 测试 Walk 函数。

函数 tree.New(k) 构造了一个随机结构的二叉树，保存了值 k，2k，3k，...，10k。 创建一个新的 channel ch 并且对其进行步进：

go Walk(tree.New(1), ch)

然后从 channel 中读取并且打印 10 个值。应当是值 1，2，3，...，10。

3. 用 Walk 实现 Same 函数来检测是否 t1 和 t2 存储了相同的值。

4. 测试 Same 函数。

Same(tree.New(1), tree.New(1)) 应当返回 true，而 Same(tree.New(1), tree.New(2)) 应当返回 false。
*/
